import java.util.Stack;

public class Trap {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            if (stack.isEmpty() || height[i] < height[stack.peek()]) {
                stack.add(i);
                continue;
            }else {
                if (stack.size() < 2) {
                    stack.pop();
                }else {
                    while (height[i] > height[stack.peek()]) {
                        int mid = stack.pop();
                        if (stack.isEmpty()) break;
                        int left = stack.peek();
                        sum += (i - left - 1) * (Math.min(height[left], height[i])-height[mid]);
                    }
                }
            }
            stack.add(i);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        Trap trap = new Trap();
        System.out.println(trap.trap(height));
    }
}
